package com.mgq.algorithm.forcerecursive;

/**
 * @author MaGuangQi
 * 规定1和A对应、2和B对应、3和C对应...
 * 那么一个数字字符串比如"111"，就可以转化为"AAA"、"KA" 和"AK"。
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
 * @date 2022-01-07 15:07
 **/
public class PrintAllStr {
    public static void main(String[] args) {
        char[] str = {'2', '6', '1', '5'};  //2,6,1,5 // 26,1,5 //26,15 //2,6,15
        int process = process(str, 0);
        int process2 = process2(str, 0);
        int process3 = dp(str);
        System.out.println(process);
        System.out.println(process2);
        System.out.println(process3);
    }

    private static int process(char[] str, int i) {
        if (i == str.length) {
            return 1;
        }
        //0开头,无法转化,返回0
        if (str[i] == '0') {
            return 0;
        }
        if (str[i] == '1') {
            int result = process(str, i + 1);
            if (i + 1 < str.length) {
                result += process(str, i + 2);
            }
            return result;
        }
        if (str[i] == '2') {
            int result = process(str, i + 1);
            if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                result += process(str, i + 2);
            }
            return result;
        }
        return process(str, i + 1);
    }

    /**
     * 第二种方法
     *
     * @param str
     * @param index
     * @return
     */
    private static int process2(char[] str, int index) {
        if (index == str.length) {
            //找到了一种方式
            return 1;
        }
        //index为0
        if (str[index] == '0') {
            return 0;
        }
        //处理 index的值是1-9
        int res = process2(str, index + 1);
        //到最后了,没有第二种可能
        if (index == str.length - 1) {
            return res;
        }
        //没有到最后,index和index+1构成一个整体,看有多少种情况
        if ((str[index] - '0') * 10 + (str[index + 1] - '0') < 27) {
            res += process2(str, index + 2);
        }
        return res;
    }

    /**
     * dp版本
     *
     * @param str
     * @return
     */
    private static int dp(char[] str) {
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        dp[N - 1] = str[N-1] == '0' ? 0 : 1;
        for (int i = N - 2; i >= 0; i--) {
            dp[i] = dp[i + 1];
            if ((str[i] - '0') * 10 + (str[i + 1] - '0') < 27) {
                dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }

}
